TNotes.leetcode

Appearance

0999. 可以被一步捕获的棋子数【简单】

0999. 可以被一步捕获的棋子数【简单】 ​

1. 📝 题目描述 ​

给定一个 8 x 8 的棋盘，只有一个 白色的车，用字符 'R' 表示。棋盘上还可能存在白色的象 'B' 以及黑色的卒 'p'。空方块用字符 '.' 表示。

车可以按水平或竖直方向（上，下，左，右）移动任意个方格直到它遇到另一个棋子或棋盘的边界。如果它能够在一次移动中移动到棋子的方格，则能够 吃掉 棋子。

注意：车不能穿过其它棋子，比如象和卒。这意味着如果有其它棋子挡住了路径，车就不能够吃掉棋子。

返回白车 攻击 范围内 兵的数量。

示例 1：

img

txt
输入：[
  [".", ".", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", "p", ".", ".", ".", "."],
  [".", ".", ".", "R", ".", ".", ".", "p"],
  [".", ".", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", "p", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", ".", "."]
]

输出：3
解释：
在本例中，车能够吃掉所有的卒。

示例 2：

img

txt
输入：[
  [".", ".", ".", ".", ".", ".", ".", "."],
  [".", "p", "p", "p", "p", "p", ".", "."],
  [".", "p", "p", "B", "p", "p", ".", "."],
  [".", "p", "B", "R", "B", "p", ".", "."],
  [".", "p", "p", "B", "p", "p", ".", "."],
  [".", "p", "p", "p", "p", "p", ".", "."],
  [".", ".", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", ".", "."]
]

输出：0
解释：
象阻止了车吃掉任何卒。

示例 3：

img

txt
输入：[
  [".", ".", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", "p", ".", ".", ".", "."],
  [".", ".", ".", "p", ".", ".", ".", "."],
  ["p", "p", ".", "R", ".", "p", "B", "."],
  [".", ".", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", "B", ".", ".", ".", "."],
  [".", ".", ".", "p", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", ".", "."]
]

输出：3
解释：
车可以吃掉位置 b5，d6 和 f5 的卒。

提示：

  1. board.length == 8
  2. board[i].length == 8
  3. board[i][j] 可以是 'R'，'.'，'B' 或 'p'
  4. 只有一个格子上存在 board[i][j] == 'R'

2. 🎯 s.1 - 直线扫描（四方向） ​

js
/**
 * @param {string[][]} board
 * @return {number}
 */
var numRookCaptures = function (board) {
  let rx = -1,
    ry = -1
  for (let i = 0; i < 8; i++) {
    for (let j = 0; j < 8; j++) {
      if (board[i][j] === 'R') {
        rx = i
        ry = j
        break
      }
    }
    if (rx !== -1) break
  }

  let count = 0
  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ]

  for (const [dx, dy] of dirs) {
    let x = rx + dx,
      y = ry + dy
    while (x >= 0 && x < 8 && y >= 0 && y < 8) {
      const cell = board[x][y]
      if (cell === 'B') break
      if (cell === 'p') {
        count++
        break
      }
      x += dx
      y += dy
    }
  }

  return count
}
  • 时间复杂度：O(1)（棋盘固定为 8×8）
  • 空间复杂度：O(1)

算法思路：

  • 先定位白车位置
  • 随后在上下左右四个方向直线扫描：
    • 遇到象 B 停止扫描
    • 若首先遇到卒 p，计数加一并停止扫描
    • 越界停止扫描

Discussions